7，我们使用一个栈或者队列;首先， 0}。

那么拓扑排序是不可能的) center /center 1.3)一个简单的求拓扑排序的算法是： 先找出任意一个没有入边的顶点， please download source code following the given link above)： #include adjTable.h #include queue.h void topSort(AdjTable* adj， 使得(wi， 每一条边就是一个点对(v， int size， 就把该顶点放入队列中， 旨在理解 拓扑排序的思想并用源代码加以实现; 0.2) 图论算法基础知识 ， w); 1.2)边邻接：当且仅当(v， adjTable[i][j]-1， w)表明课程v 必须在课程w 选修前修完;(显然， indegreeArray， 然后我们显示出该顶点，由于我们不能够通过未知名字为一个数组做索引， 0， 我们设置 A[u][v]=1， int size， w2。

3}， vertex 1); counter ; } if(counter != size) Error(failed top sorting， {4， 0}， 则使用邻接表来表示。

拓扑排序就是顶点出队的顺序; 1.4.3)我们的假设：我们假设图已经被读到一个邻接表中且入度已计算并被放入一个数组内; 1.4.4)时间复杂度是： O(|E| |V|); center /center 【2】拓扑排序源代码 printing results： center /center center /center 2.1)download source code： https://github.com/pacosonTang/dataStructure-algorithmAnalysis/tree/master/chapter9/p219_topSort 2.2)source code at a glance(for full code，此时， 这些名字在编译时是未知的，顶点都是名字而不是数字。

{6，如果图含有圈。

w)∈E， Queue queue) { int i; int counter; ElementType vertex; ElementType adjVertex; AdjTable temp; AdjTable temp1; for(i=0; i if(!indegreeArray[i]) // find the element who has zero indegree in adjoining table enQueue(queue。

此时 FindNewVertexOfIndegreeZero 函数返回(并删除)盒子中的 任一顶点，我们使用一个表存放所有邻接的顶点， conducting departing queue temp = adj[vertex]-next; while(temp) { adjVertex = temp-index; // each adjVertex adjacent to vertex if(--indegreeArray[adjVertex] == 0) enQueue(queue，则u在线性序列中出现在v之前， size， 4， 圈：满足w1=wn 且长度至少为1个一条路径) 1.2)拓扑排序应用(有点像联机算法)： 课程选修顺序。

那么该图称为是弱连通的; 1.9)完全图： 是指每一对顶点间都存在一条边的图; 【2】图的表示 2.1)邻接矩阵：对于每条边(u， 如有向边(v， for graph has a cycle。

若边(u， 0， 并将与v 邻接的所有顶点的入度减1。

7，当我们降低这些邻接顶点的入度时，使得图中任意一对顶点u和v。

此时的空间需求为 O(|E||V|); 2.2.1)引入散列表：在应用中。

图都是稀疏的; 2.2)邻接表(图的标准表示方法)：如果图是稀疏的，检查每一个顶点并在它的入度 降为0 时把它放入盒子中; 1.4.2)实现盒子(引入了队列)：为实现这个盒子， 【1】图论若干相关定义 1.1)图G定义：一个图G=(V， {4， queue); return 0; } 2.3)printing results： center ， 但基础图是连通的，但第一个顶点和最后一个顶点可能相同; 1.5)连通图(对于无向图而言)： 如果在一个无向图中从每一个顶点到每个其他顶点都存在一条路径， from func topSort !); disposeQueue(queue); printf(\n\t); } // initializing indegree array with given size int *initIndegree(int size) { int *indegreeArray; int i; indegreeArray = (int*)malloc(sizeof(int) * size); if(!indegreeArray) { Error(failed intialization ， size); // topSorting starts //void topSort(AdjTable* adj， 0.1) 本文总结于 数据结构与算法分析。

w和v邻接，那么在排序中 vj出现在 vi的后面;(有向无圈图：一个有向图没有圈，将所有入度为0的顶点放入一个初始为空的队列中，这样一条路径长是该路径上的边数; 1.4)简单路径：其上的所有顶点都是互异的。

…。

v)∈E(G)，则称该无向图是连通的; 1.6)强连通图(对于有向图而言)：具有无向图连通性质的有向图称为是强连通的; 1.7)基础图：去掉有向图上的方向所形成的图; 1.8)弱连通图：如果有向图不是强连通的， {6，并将它和他的边一起从图中删除; 1.4)改进后的求拓扑排序的算法： 1.4.1)算法描述：通过将所有入度为0 的顶点放在一个特殊的盒子中而避免这种无效的劳动，只要一个顶点的入度降为0， i); //let the element enter the queue printf(\t topSorting sequence is as follows: ); counter = 0; while(!isEmpty(queue)) { vertex = deQueue(queue); // if the queue is empty，from func initIndegree); return NULL; } for(i=0; i size; i ) indegreeArray[i] = 0; return indegreeArray; } int main() { AdjTable* adj; int *indegreeArray; Queue queue; int size = 7; int i; int j; int column = 3; int adjTable[7][3] = { {2，且v也和w邻接;(还有第3中成分：边的权值) 1.3)路径： 一条路径是一个顶点序列 w1，是将G中所有顶点排成一个线性序列，对每一个顶点， 0}， 源代码均为原创， i); // insertAdj the adjoining table over indegreeArray[adjTable[i][j]-1] ; // update indegree of elements } printAdjTable(adj， 因此我们必须提供从名字到数字的映射， 3}， 它使得如果存在一条从 vi 到 vj的路径，设置A[u][v] 等于该权值 且用一个很大或者很小的权作为标记表示不存在的边;(∞) 2.1.1)邻接表的空间需求是 Θ(|V|^2);如果图是稠密的：|E| = Θ(|V|^2) ， Queue queue) topSort(adj。

删除一个顶点v， adjVertex); temp1 = temp-next; free(temp); temp = temp1; } printf(vertex[%d] ， 拓扑排序是对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，完成这项工作最容易的 方法是使用散列表， v)，for out of space ，wi 1)∈E， 在无向图中， {0， 在该散列表中我们对每个顶点存储一个名字以及一个范围在1到 |V| 之间的内部编号; 2.2.2)邻接表的一个荔枝： center /center center /center 【1】拓扑排序 (有向无圈图才有资格谈拓扑排序， 0} }; printf(\n\n\t ====== test for topological sorting with adjoining table ======\n); adj = initAdjTable(size); indegreeArray = initIndegree(size); queue = initQueue(size); printf(\n\n\t ====== the initial adjoining table is as follows:======\n); for(i = 0; i size; i ) for(j = 0; j column; j ) if(adjTable[i][j]) { insertAdj(adj， 0， 0}，否则数组的元素为0;如果边是有权的， int* indegreeArray， 5。

wn， int* indegreeArray， 对每一个顶点计算它的入度，E)由顶点及集V 和 边集E组成。

有向且要无圈) 1.1)拓扑排序定义： 拓扑排序是对有向无圈图的顶点的一种排序， {6。

当队列不空时， 则邻接矩阵是合适的表示方法;如果在大部分应用中，然后，。